/*
 * Copyright (c) 2009, Andrey Shvetsov
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

#include <iostream>
#include <iterator>
#include <iomanip>
#include <algorithm>
#include <functional>

#include <xintlibio.h>
#include <xintlib.h>

using namespace std;

namespace perf_test {

using xintlib::hex2xint;
using xintlib::xint;
using xintlib::for_each_unit;
using xintlib::for_each_unit_r;


typedef xint<3000> xxint;


enum side_t { LEFT_SIDE, RIGHT_SIDE };

template <class T>
struct superholder {
    superholder(const T &subholder, xxint number, side_t side):
        _subholder( subholder ), _number( number ), _side( side ) {}

    void print(side_t side) const {
        if( _side == side )
            cout << xintlib::hex( " " ) << _number << endl;
        _subholder.print( side );
    }

private:
    const T &_subholder;
    const xxint _number;
    const side_t _side;
};

struct empty_holder {
    void print(side_t) const {}
};


int operations_number = 0;


template <int N, class T = empty_holder>
struct level {
    typedef superholder<T> next_holder;
    typedef level<N-1,next_holder> next_level;

    static void put_right(const xxint *a, xxint restl, xxint restr, const T &holder = empty_holder()) {
        operations_number++;
        next_level::search( a+1, restl, restr - *a, next_holder( holder, *a, RIGHT_SIDE ) ); }

    static void put_left(const xxint *a, xxint restl, xxint restr, const T &holder = empty_holder()) {
        operations_number++;
        next_level::search( a+1, restl - *a, restr, next_holder( holder, *a, LEFT_SIDE ) ); }

    static void search(const xxint *a, xxint restl, xxint restr, const T &holder) {
        if( *a <= restr )
            put_right( a, restl, restr, holder );
        if( *a <= restl )
            put_left( a, restl, restr, holder );
    }
};


template <class T>
struct level<0,T> {
    static void search(const xxint *a, xxint restl, xxint restr, const T &holder)
    {
        holder.print( LEFT_SIDE ); cout << "==" << endl; holder.print( RIGHT_SIDE );
        cout << "(" << operations_number << ")" << endl;
    }
};


template <int N> xxint sum(const xxint *a) { return *a + sum<N-1>( a + 1 ); };
template <> xxint sum<0>(const xxint *) { return 0; }

template <class XINT>
struct half_maker {
    typedef typename XINT::unit_type unit_type;

    half_maker(): _bit(0) {}
    
    void operator()(unit_type &u) {
        unsigned const bit = u&1;
        u = ( unit_type(_bit) << (XINT::BITS_PRO_UINT-1) ) | ( u>>1 );
        _bit = bit;
    }
protected:
    int _bit;
};

template <class T, int N>
static void search(T (&a)[N])
{
    operations_number = 0;

    xxint halfsum = sum<N>( a ); half_maker<xxint> hm; for_each_unit( halfsum, hm );
    sort( a, a+N, greater<xxint>() );
    level<N>::put_right( a, halfsum, halfsum );
    cout << "total operations: " << operations_number << endl;
    cout << endl;
}


// converts number from <small number: VALUE> to
// <big number: 00000000 A1B2C3D4 ... A1B2C3D4 VALUE>
template <class XINT>
struct big_maker
{
    typedef typename XINT::unit_type unit_type;

    big_maker(unsigned value): _value(value), _counter(0) {}

    void operator()(unit_type &u) {
        switch( ++_counter ) {
        case 1: u = _value; break;
        case XINT::N: u = 0; break;
        default: u = 0xa1b2c3d4; break;
        }
    }
private:
    unsigned const _value;
    int _counter;
};

// converts each number from src[N] to dest[N] using big_maker
template <int N>
static void convert(const unsigned *src, xxint *dest)
{
    big_maker<xxint> bm( *src );
    for_each_unit_r( *dest, bm );
    convert<N-1>( src+1, dest+1 );
}

template <>
static void convert<0>(const unsigned *, xxint *) {}

template <int N>
static void make_big_n_search(unsigned (&a)[N])
{
    xxint xa[N];
    convert<N>( a, xa );
    search( xa );
}

unsigned perf_test[] = {
    62, 83, 121, 281, 486, 538, 734, 771, 854, 885, 921, 975, 1000, 1111,
    62, 83, 121, 281, 486, 538, 734, 771, 854, 885, 921, 975, 1000, 1111,
    1
};

int full_search()
{
    make_big_n_search( perf_test );

    return 0;
}

} // namespace perf_test
